
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <Stdbool.h>
  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };
 
int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    else
        return 1+TreeSize(root->left)+TreeSize(root->right);
}

void prevTree(struct TreeNode* root,int* a,int* n)
{
    if(root==NULL)
        return ;
    a[(*n)]=root->val;
    (*n)++;
    prevTree(root->left,a,n);
    prevTree(root->right,a,n);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    int num=TreeSize(root);
    *returnSize=num;
    if(num==0)
        return NULL;
    int n=0;
    int* a=(int*)malloc(sizeof(int)*num);
    prevTree(root,a,&n);
    return a;
    
}